package com.leetcode.partition13;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/11/2 10:12
 */
public class LC1248统计优美子数组 {

    public static int numberOfSubarrays(int[] nums, int k) {
        return prefixSum(nums, k);
    }

    public static void main(String[] args) {
        int[] nums = {2, 4, 6, 1, 2, 2, 1, 2, 2, 2};
        int k = 2;
        System.out.println(numberOfSubarrays(nums, k));
    }

    private static int prefixSum(int[] nums, int k) {
        //prefix[i]记录nums[0]到nums[i-1]为奇数的个数
        int prefixSums = 0, answer = 0;
        //记录前缀和prefix[i]出现的次数
        int[] count = new int[nums.length + 1];
        count[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            prefixSums += nums[i] & 1;
            //prefix[j]-prefix[i]=k -> prefix[i]=prefix[j]-k
            if (prefixSums >= k) answer += count[prefixSums - k];
            count[prefixSums]++;
        }
        System.out.println(Arrays.toString(count));
        return answer;
    }
}
